from typing import List


class Solution:
    """
    方法：使用单调栈解决每日温度问题
    Args:
        temperatures: List[int] - 每日温度列表
    Returns:
        List[int] - 每个温度需要等待多少天才能遇到更高温度的结果列表
    Time: O(n) - 每个元素最多入栈和出栈一次
    Space: O(n) - 最坏情况下栈的大小为n
    """
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans =[0] * n
        st = []
        for i, t in enumerate(temperatures):
            while st and t > temperatures[st[-1]]:
                j = st.pop()
                ans[j] = i - j
            st.append(i)
        return ans
    
    """
    方法：使用单调栈从后向前解决每日温度问题
    Args:
        temperatures: List[int] - 每日温度列表
    Returns:
        List[int] - 每个温度需要等待多少天才能遇到更高温度的结果列表
    Time: O(n) - 每个元素最多入栈和出栈一次
    Space: O(n) - 最坏情况下栈的大小为n
    """
    def dailyTemperatures1(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans =[0] * n
        st = []
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            while st and t >= temperatures[st[-1]]:
                st.pop()
            if st:
                 ans[i] = st[-1] - i
            st.append(i)
        return ans